Network routers control the flow of data traffic in networks, between networks and between networks and end users. Basic information on routers and their use in networks is disclosed by Radia Perlman in the book entitled INTERCONNECTIONS, the second edition of which was published by Addison-Wesley in 1999.
FIG. 1A shows the structure of a typical router 10. The router is composed of a number of channel cards 12 connected to the backplane 14. The channel cards receive packets of data from and transmit packets of data to the user or the network. The channel cards additionally receive packets of data from and transmit packets of data to the backplane. The packets of data transmitted to or from the backplane differ from those transmitted to and from the network or user and will be called envelopes to distinguish them.
The backplane 14 transmits envelopes of data received from any of the channel cards 12 to a specific channel of any of the channel cards in accordance with a channel address included in the header of the envelopes. The channel card determines the channel address in response to destination address data in the headers of the packets and address information stored in the address table 16. The address table is hierarchical and stores address information that indicates the network or user connections made to each channel of the router 10. The address information is detailed with respect to the domains of users connected to the channels and are more general with respect to networks connected to the channels.
FIG. 1B shows details of the exemplary channel card 12. The channel card is composed of the transmitter/receiver 20, the packet processing engine (PPE) 22, the address memory 24 and the output queue buffer 26. More than one transmitter/receiver may be connected to the packet processing engine, in which case the channel card handles more than one channel. In some applications, the transmitter/receiver may be a transmitter only or a receiver only and the term transmitter/receiver will be understood to cover all these possibilities.
The transmitter/receiver (TX/RX) 20 transmits packets of data to, and receives packets of data from, the user or the network connected to it. The transmitter/receiver receives packets of data for transmission from, and transmits received packets of data to, the packet processing engine 22.
The address memory 24 stores all, or a subset of, the address information stored in the address table 16 (FIG. 1A). The address information is transferred from the address table to the address memory via the backplane 14 and the PPE 22. The address information indicates the network address of the network device connected to each of the channels of the router 10. For example, the address information might indicate that a packet with a particular destination address should be transmitted to the m-th channel on channel card n.
The PPE 22 performs a framing operation on the data stream received from the transmitter/receiver 20 to determine the boundaries of the packets. Once the boundaries of the packets are determined, the PPE performs a header read operation to read the header of each packet. The header includes data indicating the destination, in network terms, of the packet and the length of the packet. The PPE inserts the packet into one or more envelopes suitable for transmission through the router 10. For example, the envelopes may be packet-like structures having a fixed length.
The PPE 22 additionally reads the destination address from the header of the packet and, using address data read from the address memory 24 determines a destination channel in the router 10 for the envelopes derived from the packet. The PPE adds a header to each envelope indicating the address of the destination channel, and feeds the envelopes to the output queue 26. The output queue temporarily stores the envelopes until they can be transmitted via the backplane 14 to the destination channel.
In the destination channel, the PPE 22 regenerates the packets from their respective envelopes and feeds them to the transmitter/receiver 20, whence they are transmitted to the network or user. The packets may be stored in a transmit queue (not shown) prior to transmission.
The router architecture just described has a number of aspects that can limit its performance. For example, the internal queues can delay data through the router if the data routes connected to the router are busy. Moreover, packets can be lost if the quantity of data received for transmission to a given destination exceeds the quantity of data that can be transmitted to this destination. Lost or discarded packets are generally acceptable in a conventional data transmission environment in which consequences of lost or delayed packets are relatively minor. For example, the receiver can simply request that a lost packet be re-transmitted. However, lost or delayed packets can be an issue for certain services, such as when the network is used to transmit packets of audio and video data, or when the network owner has entered into a service level agreement in which a given quality of service is guaranteed to a user.
It would be advantageous to increase the performance of the conventional router in a number of additionally aspects, for example:                to provide a metering capability that does not seriously degrade the speed of the router. Such a capability would enable a user connected to the router to be billed for the quantity of data transmitted or received from the network and could optionally additionally provide the customer with data indicating the quality of service provided;        to provide an enhanced capability for monitoring conformance with a service level agreement;        to provide an enhanced capability to police network traffic and to reject attacks from hackers;        to provide an ability to provide data for use in traffic engineering. For example, to determine the need to equip the network with additional or alternative hardware to deal with increased traffic or changed traffic patterns; and        to provide an ability to alter variable routing topologies to take account of existing traffic. Conventionally, when large quantities of data are distributed among multiple routes, the routing pattern is fixed in advance and therefore cannot take into account the traffic sharing each route. For example, round-robin sequencing between multiple routes is often used.        
A key to providing the above capabilities is to gather data characterizing the data transmission performance of the router and of the network. Some routers include rudimentary systems for collecting monitoring data, but the monitoring data generated by such data collection systems have such a high granularity that bursty traffic is significantly under-recorded. It is bursty traffic that most seriously taxes the transmission capabilities of a network. More sophisticated monitoring data can be collected using external test devices, such as the test devices sold under the brand names acceSS7 and accessATM/IP by Agilent Technologies, Inc., the assignee of this disclosure. However, such test devices are inconvenient to use because the interruption of the connections between the channel cards of the router and the network or user. Moreover, such text devices are expensive since they duplicate a substantial portion of the circuitry of the router. It would be expensive to use such test devices to monitor the performance of the number of routers that would be required to provide an accurate picture of the network performance and to provide the above additional features.
Thus, what is needed is a router having inexpensive, built-in monitoring data gathering so that one or more of the above capabilities can be provided. What is also needed is such a router whose built-in monitoring data gathering easily scales as the speed and throughput of succeeding generations of routers increase in response to the exponential growth in network traffic. What is also needed is a router having built-in monitoring data gathering in which minimal modifications to the existing router architecture is required.